package com.sheng.leetcode.year2022.month05.day07;

import org.junit.Test;

import java.util.*;

/**
 * @author liusheng
 * @date 2022/05/07
 *
 * 433. 最小基因变化
 *
 * 基因序列可以表示为一条由 8 个字符组成的字符串，其中每个字符都是 'A'、'C'、'G' 和 'T' 之一。
 * 假设我们需要调查从基因序列 start 变为 end 所发生的基因变化。一次基因变化就意味着这个基因序列中的一个字符发生了变化。
 * 例如，"AACCGGTT" --> "AACCGGTA" 就是一次基因变化。
 * 另有一个基因库 bank 记录了所有有效的基因变化，只有基因库中的基因才是有效的基因序列。
 * 给你两个基因序列 start 和 end ，以及一个基因库 bank ，请你找出并返回能够使 start 变化为 end 所需的最少变化次数。如果无法完成此基因变化，返回 -1 。
 * 注意：起始基因序列 start 默认是有效的，但是它并不一定会出现在基因库中。
 *
 * 示例 1：
 *
 * 输入：start = "AACCGGTT", end = "AACCGGTA", bank = ["AACCGGTA"]
 * 输出：1
 * 示例 2：
 *
 * 输入：start = "AACCGGTT", end = "AAACGGTA", bank = ["AACCGGTA","AACCGCTA","AAACGGTA"]
 * 输出：2
 * 示例 3：
 *
 * 输入：start = "AAAAACCC", end = "AACCCCCC", bank = ["AAAACCCC","AAACCCCC","AACCCCCC"]
 * 输出：3
 *
 * 提示：
 *
 * start.length == 8
 * end.length == 8
 * 0 <= bank.length <= 10
 * bank[i].length == 8
 * start、end 和 bank[i] 仅由字符 ['A', 'C', 'G', 'T'] 组成
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/minimum-genetic-mutation
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class LeetCode0433 {

    @Test
    public void test01(){
//        String start = "AACCGGTT", end = "AACCGGTA";
//        String[] bank = {"AACCGGTA"};
        String start = "AACCGGTT", end = "AAACGGTA";
        String[] bank = {"AACCGGTA","AACCGCTA","AAACGGTA"};
//        String start = "AAAAACCC", end = "AACCCCCC";
//        String[] bank = {"AAAACCCC","AAACCCCC","AACCCCCC"};
//        String start = "AACCGGTT", end = "AACCGGTA";
//        String[] bank = {};
//        String start = "AACCTTGG", end = "AATTCCGG";
//        String[] bank = {"AATTCCGG","AACCTGGG","AACCCCGG","AACCTACC"};
        System.out.println(new Solution().minMutation(start, end, bank));
    }

}
class Solution {
    /**
     * 每次修改只能修改一位字符，每次修改的结果都必须存在于基因库bank中
     */
    char[] items = new char[]{'A', 'C', 'G', 'T'};

    /**
     * bfs的思想，将每一次能修改的结果都存起来，查询完第一次能修改的之后再查询第二次...，这样查询出来第一个满足条件的路径，就是最少的修改次数之一
     */
    public int minMutation(String start, String end, String[] bank) {
        //set作为基因库，后续用来判断修改后的字符串是否存在于set中
        Set<String> set = new HashSet<>();
        Collections.addAll(set, bank);
        //修改一次之后的字符串的样子
        Deque<String> d = new ArrayDeque<>();
        //记录每一个修改后并存在于基因库的字符串，并记录他的修改次数
        Map<String, Integer> map = new HashMap<>(16);
        d.addLast(start);
        map.put(start, 0);
        //如果队列不为空则进行循环
        while (!d.isEmpty()) {
            //获取队列的长度
            int size = d.size();
            //队列长度如果大于0，则进入循环体，同时将长度减一
            while (size-- > 0) {
                String s = d.pollFirst();
                char[] cs = s.toCharArray();
                //获取当前字符串的修改次数，step代表修改次数
                Integer step = map.get(s);
                //字符串总长度为8，对每一个位置进行循环
                for (int i = 0; i < 8; i++) {
                    //循环4个字符，在当前位置进行修改，并判断是否存在于基因库中
                    for (char c : items) {
                        //如果当前位置的字符相等则退出
                        if (cs[i] == c) {
                            continue;
                        }
                        //不相同则可以进行修改
                        char[] clone = cs.clone();
                        //将当前位置的字符修改
                        clone[i] = c;
                        //生成修改后的新字符串
                        String sub = String.valueOf(clone);
                        //判断是否存在于set中,不存在则结束
                        if (!set.contains(sub)) {
                            continue;
                        }
                        //判断是否存在于map中,存在则结束
                        if (map.containsKey(sub)) {
                            continue;
                        }
                        //修改后的字符串要求存在于set集合中，即存在于bank基因库中，还要不能在map中出现过,才能走到这一步
                        //如果修改后的字符串和end相等，则修改完毕
                        if (sub.equals(end)) {
                            //代表当前这次为最后一次修改，即前面的修改次数step加上本次，为step + 1
                            return step + 1;
                        }
                        //不相等，意味这又进行了一次修改
                        map.put(sub, step + 1);
                        //将修改后的字符串放进队列中，后续以修改后的字符串为原点进行修改
                        d.addLast(sub);
                    }
                }
            }
        }
        return -1;
    }
}

//class Solution {
//    static char[] items = new char[]{'A', 'C', 'G', 'T'};
//    public int minMutation(String S, String T, String[] bank) {
//        Set<String> set = new HashSet<>();
//        Collections.addAll(set, bank);
//        Deque<String> d = new ArrayDeque<>();
//        Map<String, Integer> map = new HashMap<>();
//        d.addLast(S);
//        map.put(S, 0);
//        while (!d.isEmpty()) {
//            int size = d.size();
//            while (size-- > 0) {
//                String s = d.pollFirst();
//                char[] cs = s.toCharArray();
//                int step = map.get(s);
//                for (int i = 0; i < 8; i++) {
//                    for (char c : items) {
//                        if (cs[i] == c) {
//                            continue;
//                        }
//                        char[] clone = cs.clone();
//                        clone[i] = c;
//                        String sub = String.valueOf(clone);
//                        if (!set.contains(sub)) {
//                            continue;
//                        }
//                        if (map.containsKey(sub)) {
//                            continue;
//                        }
//                        if (sub.equals(T)) {
//                            return step + 1;
//                        }
//                        map.put(sub, step + 1);
//                        d.addLast(sub);
//                    }
//                }
//            }
//        }
//        return -1;
//    }
//}
//
//作者：AC_OIer
//链接：https://leetcode-cn.com/problems/minimum-genetic-mutation/solution/by-ac_oier-74b4/
//来源：力扣（LeetCode）
//著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
